package OptimalAlgorithm.DivideAndConquer_Quicksort;

import java.util.Random;
//https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/
public class InventoryManagement {
    public int[] inventoryManagement(int[] stock, int cnt) {
        int[] ret = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            ret[i] = qsort(stock,0,stock.length - 1,i + 1);
        }
        return ret;
    }

    private int qsort(int[] stock, int l, int r, int k) {
        Random random = new Random();
        int key = stock[random.nextInt(stock.length) % (r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        while (i <= right - 1){

            if(stock[i] == key){
                i++;
            }else if(stock[i] < key){
                swap(left + 1,i,stock);
                i++;
                left++;
            }else {
                swap(right - 1,i,stock);
                right--;
            }
        }
        if(left - l + 1 >= k){
            return qsort(stock,l,left,k);
        }else if(right - l >= k){
            return key;
        }else {
            return qsort(stock,right,r,k - (right - l));
        }
    }
    private void swap(int i,int j,int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    /*    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock,0,stock.length - 1,cnt);
        int[] ret = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            ret[i] = stock[i];
        }
        return ret;
    }

    private void qsort(int[] stock, int l, int r, int k) {
        if(l >= r){
            return;
        }
        Random random = new Random();
        int key = stock[random.nextInt(stock.length) % (r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        while (i <= right - 1){

            if(stock[i] == key){
                i++;
            }else if(stock[i] < key){
                swap(left + 1,i,stock);
                i++;
                left++;
            }else {
                swap(right - 1,i,stock);
                right--;
            }
        }
        if(left - l + 1 >= k){
             qsort(stock,l,left,k);
        }else if(right - l >= k){
            return;
        }else {
             qsort(stock,right,r,k - (right - l));
        }
    }
    private void swap(int i,int j,int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }*/
}
